
<!DOCTYPE html>

<html>
  
<!-- Mirrored from docs.sympy.org/latest/modules/combinatorics/fp_groups.html by HTTrack Website Copier/3.x [XR&CO'2014], Sat, 15 Jan 2022 03:28:18 GMT -->
<!-- Added by HTTrack --><meta http-equiv="content-type" content="text/html;charset=utf-8" /><!-- /Added by HTTrack -->
<head>
    <meta charset="utf-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" /><meta name="generator" content="Docutils 0.17.1: http://docutils.sourceforge.net/" />

    <title>Finitely Presented Groups &#8212; SymPy 1.9 documentation</title>
    <link rel="stylesheet" type="text/css" href="../../_static/pygments.css" />
    <link rel="stylesheet" type="text/css" href="../../_static/default.css" />
    <link rel="stylesheet" type="text/css" href="../../_static/graphviz.css" />
    <link rel="stylesheet" type="text/css" href="../../_static/plot_directive.css" />
    <link rel="stylesheet" type="text/css" href="../../../../live.sympy.org/static/live-core.css" />
    <link rel="stylesheet" type="text/css" href="../../../../live.sympy.org/static/live-autocomplete.css" />
    <link rel="stylesheet" type="text/css" href="../../../../live.sympy.org/static/live-sphinx.css" />
    
    <script data-url_root="../../" id="documentation_options" src="../../_static/documentation_options.js"></script>
    <script src="../../_static/jquery.js"></script>
    <script src="../../_static/underscore.js"></script>
    <script src="../../_static/doctools.js"></script>
    <script src="../../../../live.sympy.org/static/utilities.js"></script>
    <script src="../../../../live.sympy.org/static/external/classy.js"></script>
    <script src="../../../../live.sympy.org/static/live-core.js"></script>
    <script src="../../../../live.sympy.org/static/live-autocomplete.js"></script>
    <script src="../../../../live.sympy.org/static/live-sphinx.js"></script>
    <script async="async" src="../../../../cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.5/latest8331.js?config=TeX-AMS_HTML-full"></script>
    <script type="text/x-mathjax-config">MathJax.Hub.Config({"tex2jax": {"inlineMath": [["\\(", "\\)"]], "displayMath": [["\\[", "\\]"]]}})</script>
    
    <link rel="shortcut icon" href="../../_static/sympy-notailtext-favicon.ico"/>
    <link href="fp_groups.html" rel="canonical" />
    
    <link rel="index" title="Index" href="../../genindex.html" />
    <link rel="search" title="Search" href="../../search.html" />
    <link rel="next" title="Polycyclic Groups" href="pc_groups.html" />
    <link rel="prev" title="Tensor Canonicalization" href="tensor_can.html" /> 
  </head><body>
    <div class="related" role="navigation" aria-label="related navigation">
      <h3>Navigation</h3>
      <ul>
        <li class="right" style="margin-right: 10px">
          <a href="../../genindex.html" title="General Index"
             accesskey="I">index</a></li>
        <li class="right" >
          <a href="../../py-modindex.html" title="Python Module Index"
             >modules</a> |</li>
        <li class="right" >
          <a href="pc_groups.html" title="Polycyclic Groups"
             accesskey="N">next</a> |</li>
        <li class="right" >
          <a href="tensor_can.html" title="Tensor Canonicalization"
             accesskey="P">previous</a> |</li>
        <li class="nav-item nav-item-0"><a href="../../index.html">SymPy 1.9 documentation</a> &#187;</li>
          <li class="nav-item nav-item-1"><a href="../index.html" >SymPy Modules Reference</a> &#187;</li>
          <li class="nav-item nav-item-2"><a href="index.html" accesskey="U">Combinatorics</a> &#187;</li>
        <li class="nav-item nav-item-this"><a href="#">Finitely Presented Groups</a></li> 
      </ul>
    </div>  

    <div class="document">
      <div class="documentwrapper">
        <div class="bodywrapper">
          <div class="body" role="main">
            
  <section id="finitely-presented-groups">
<h1>Finitely Presented Groups<a class="headerlink" href="#finitely-presented-groups" title="Permalink to this headline">¶</a></h1>
<section id="introduction">
<h2>Introduction<a class="headerlink" href="#introduction" title="Permalink to this headline">¶</a></h2>
<p>This module presents the functionality designed for computing with finitely-
presented groups (fp-groups for short). The name of the corresponding SymPy
object is <code class="docutils literal notranslate"><span class="pre">FpGroup</span></code>. The functions or classes described here are studied
under <strong>computational group theory</strong>. All code examples assume:</p>
<div class="doctest highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">&gt;&gt;&gt; </span><span class="kn">from</span> <span class="nn">sympy.combinatorics.free_groups</span> <span class="kn">import</span> <span class="n">free_group</span><span class="p">,</span> <span class="n">vfree_group</span><span class="p">,</span> <span class="n">xfree_group</span>
<span class="gp">&gt;&gt;&gt; </span><span class="kn">from</span> <span class="nn">sympy.combinatorics.fp_groups</span> <span class="kn">import</span> <span class="n">FpGroup</span><span class="p">,</span> <span class="n">CosetTable</span><span class="p">,</span> <span class="n">coset_enumeration_r</span>
</pre></div>
</div>
<section id="overview-of-facilities">
<h3>Overview of Facilities<a class="headerlink" href="#overview-of-facilities" title="Permalink to this headline">¶</a></h3>
<p>The facilities provided for fp-groups fall into a number of natural groupings</p>
<ul class="simple">
<li><p>The construction of fp-groups using a free group and a list of words in
generators of that free group.</p></li>
<li><p>Index determination using the famous Todd-Coxeter procedure.</p></li>
<li><p>The construction of all subgroups having index less than some (small)
specified positive integer, using the <em>Low-Index Subgroups</em> algorithm.</p></li>
<li><p>Algorithms for computing presentations of a subgroup of finite index
in a group defined by finite presentation.</p></li>
</ul>
<p>For a description of fundamental algorithms of finitely presented groups
we often make use of <em>Handbook of Computational Group Theory</em>.</p>
</section>
</section>
<section id="the-construction-of-finitely-presented-groups">
<h2>The Construction of Finitely Presented Groups<a class="headerlink" href="#the-construction-of-finitely-presented-groups" title="Permalink to this headline">¶</a></h2>
<p>Finitely presented groups are constructed by factoring a free group by a
set of relators. The set of relators is taken in as a list of words in
generators of free group in SymPy, using a list provides ordering to the
relators. If the list of relators is empty, the associated free group is
returned.</p>
<p>Example of construction of a finitely-presented group.
The symmetric group of degree 4 may be represented as a two generator group
with presentation <span class="math notranslate nohighlight">\(\left\langle a, b \mid a^2, b^3, (ab)^4 \right\rangle\)</span>. Giving the relations as a
list of relators, group in SymPy would be specified as:</p>
<div class="doctest highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">&gt;&gt;&gt; </span><span class="n">F</span><span class="p">,</span> <span class="n">a</span><span class="p">,</span> <span class="n">b</span> <span class="o">=</span> <span class="n">free_group</span><span class="p">(</span><span class="s2">&quot;a, b&quot;</span><span class="p">)</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">G</span> <span class="o">=</span> <span class="n">FpGroup</span><span class="p">(</span><span class="n">F</span><span class="p">,</span> <span class="p">[</span><span class="n">a</span><span class="o">**</span><span class="mi">2</span><span class="p">,</span> <span class="n">b</span><span class="o">**</span><span class="mi">3</span><span class="p">,</span> <span class="p">(</span><span class="n">a</span><span class="o">*</span><span class="n">b</span><span class="p">)</span><span class="o">**</span><span class="mi">4</span><span class="p">])</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">G</span>
<span class="go">&lt;fp group on the generators (a, b)&gt;</span>
</pre></div>
</div>
<p>Currently groups with relators having presentation like
<span class="math notranslate nohighlight">\(\left\langle r, s, t \mid r^2, s^2, t^2, rst = str = trs \right\rangle\)</span> will have to be specified as:</p>
<div class="doctest highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">&gt;&gt;&gt; </span><span class="n">F</span><span class="p">,</span> <span class="n">r</span><span class="p">,</span> <span class="n">s</span><span class="p">,</span> <span class="n">t</span> <span class="o">=</span> <span class="n">free_group</span><span class="p">(</span><span class="s2">&quot;r, s, t&quot;</span><span class="p">)</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">G</span> <span class="o">=</span> <span class="n">FpGroup</span><span class="p">(</span><span class="n">F</span><span class="p">,</span> <span class="p">[</span><span class="n">r</span><span class="o">**</span><span class="mi">2</span><span class="p">,</span> <span class="n">s</span><span class="o">**</span><span class="mi">2</span><span class="p">,</span> <span class="n">t</span><span class="o">**</span><span class="mi">2</span><span class="p">,</span> <span class="n">r</span><span class="o">*</span><span class="n">s</span><span class="o">*</span><span class="n">t</span><span class="o">*</span><span class="n">r</span><span class="o">**-</span><span class="mi">1</span><span class="o">*</span><span class="n">t</span><span class="o">**-</span><span class="mi">1</span><span class="o">*</span><span class="n">s</span><span class="o">**-</span><span class="mi">1</span><span class="p">,</span> <span class="n">s</span><span class="o">*</span><span class="n">t</span><span class="o">*</span><span class="n">r</span><span class="o">*</span><span class="n">s</span><span class="o">**-</span><span class="mi">1</span><span class="o">*</span><span class="n">r</span><span class="o">**-</span><span class="mi">1</span><span class="o">*</span><span class="n">t</span><span class="o">**-</span><span class="mi">1</span><span class="p">])</span>
</pre></div>
</div>
<p>Obviously this is not a unique way to make that particular group, but the point
is that in case of equality with non-identity the user has to manually do that.</p>
</section>
<section id="free-groups-and-words">
<h2>Free Groups and Words<a class="headerlink" href="#free-groups-and-words" title="Permalink to this headline">¶</a></h2>
<section id="construction-of-a-free-group">
<h3>Construction of a Free Group<a class="headerlink" href="#construction-of-a-free-group" title="Permalink to this headline">¶</a></h3>
<p><code class="docutils literal notranslate"><span class="pre">free_group(&quot;gen0,</span> <span class="pre">gen1,</span> <span class="pre">...,</span> <span class="pre">gen_(n-1)&quot;)</span></code> constructs a free group <code class="docutils literal notranslate"><span class="pre">F</span></code> on
<code class="docutils literal notranslate"><span class="pre">n</span></code> generators, where <code class="docutils literal notranslate"><span class="pre">n</span></code> is a positive integer. The <span class="math notranslate nohighlight">\(i\)</span>-th generator of
<span class="math notranslate nohighlight">\(F\)</span> may be obtained using the method <code class="docutils literal notranslate"><span class="pre">.generators[i]</span></code>, <span class="math notranslate nohighlight">\(i = 0, \ldots n-1\)</span>.</p>
<div class="doctest highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">&gt;&gt;&gt; </span><span class="n">F</span><span class="p">,</span> <span class="n">x</span><span class="p">,</span> <span class="n">y</span> <span class="o">=</span> <span class="n">free_group</span><span class="p">(</span><span class="s2">&quot;x, y&quot;</span><span class="p">)</span>
</pre></div>
</div>
<p>creates a free group <code class="docutils literal notranslate"><span class="pre">F</span></code> of rank 2 and assigns the variables <code class="docutils literal notranslate"><span class="pre">x</span></code> and <code class="docutils literal notranslate"><span class="pre">y</span></code>
to the two generators.</p>
<div class="doctest highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">&gt;&gt;&gt; </span><span class="n">F</span> <span class="o">=</span> <span class="n">vfree_group</span><span class="p">(</span><span class="s2">&quot;x, y&quot;</span><span class="p">)</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">F</span>
<span class="go">&lt;free group on the generators (x, y)&gt;</span>
</pre></div>
</div>
<p>creates a free group <code class="docutils literal notranslate"><span class="pre">F</span></code> of rank 2, with tuple of generators <code class="docutils literal notranslate"><span class="pre">F.generators</span></code>,
and inserts <code class="docutils literal notranslate"><span class="pre">x</span></code> and <code class="docutils literal notranslate"><span class="pre">y</span></code> as generators into the global namespace.</p>
<div class="doctest highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">&gt;&gt;&gt; </span><span class="n">F</span> <span class="o">=</span> <span class="n">xfree_group</span><span class="p">(</span><span class="s2">&quot;x, y&quot;</span><span class="p">)</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">F</span>
<span class="go">(&lt;free group on the generators (x, y)&gt;, (x, y))</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">x</span><span class="o">**</span><span class="mi">2</span>
<span class="go">x**2</span>
</pre></div>
</div>
<p>creates a free groups <code class="docutils literal notranslate"><span class="pre">F[0]</span></code> of rank 2, with tuple of generators <code class="docutils literal notranslate"><span class="pre">F[1]</span></code>.</p>
</section>
<section id="construction-of-words">
<h3>Construction of words<a class="headerlink" href="#construction-of-words" title="Permalink to this headline">¶</a></h3>
<p>This section is applicable to words of <code class="docutils literal notranslate"><span class="pre">FreeGroup</span></code> as well as <code class="docutils literal notranslate"><span class="pre">FpGroup</span></code>.
When we say <em>word</em> in SymPy, it actually means a <a class="reference external" href="https://en.wikipedia.org/wiki/Word_(group_theory)#Reduced_words">reduced word</a> , since the
words are automatically reduced. Given a group <code class="docutils literal notranslate"><span class="pre">G</span></code> defined on <span class="math notranslate nohighlight">\(n\)</span> generators
<span class="math notranslate nohighlight">\(x_1, x_2, x_3, \ldots, x_n\)</span>, a word is constructed as
<span class="math notranslate nohighlight">\(s_1^{r_1}s_2^{r_2} \cdots s_k^{r_k}\)</span> where <span class="math notranslate nohighlight">\(s_i \in \{x_1, x_2, \ldots, x_n\}\)</span>
, <span class="math notranslate nohighlight">\(r_i \in \mathbb{Z}\)</span> for all <span class="math notranslate nohighlight">\(k\)</span>.</p>
<p>Each word can be constructed in a variety of ways, since after reduction they
may be equivalent.</p>
</section>
</section>
<section id="coset-enumeration-the-todd-coxeter-algorithm">
<h2>Coset Enumeration: The Todd-Coxeter Algorithm<a class="headerlink" href="#coset-enumeration-the-todd-coxeter-algorithm" title="Permalink to this headline">¶</a></h2>
<p>This section describes the use of coset enumeration techniques in SymPy. The
algorithm used for coset enumeration procedure is Todd-Coxeter algorithm and
is developed in Sympy using [Ho05] and [CDHW73]. The reader should consult
[CDHW73] and [Hav91] for a general description of the algorithm.</p>
<p>We have two strategies of coset enumeration <em>relator-based</em> and
<em>coset-table based</em> and the two have been implemented as
<code class="docutils literal notranslate"><span class="pre">coset_enumeration_r</span></code>, <code class="docutils literal notranslate"><span class="pre">coset_enumeration_c</span></code> respectively. The two
strategies differ in the way they make new definitions for the cosets.</p>
<p>Though from the user point of view it is suggested to rather use the
<code class="docutils literal notranslate"><span class="pre">.coset_enumeration</span></code> method of <code class="docutils literal notranslate"><span class="pre">FpGroup</span></code> and specify the <code class="docutils literal notranslate"><span class="pre">strategy</span></code>
argument.</p>
<dl class="simple">
<dt><code class="docutils literal notranslate"><span class="pre">strategy</span></code>:</dt><dd><p>(default=”relator_based”) specifies the strategy of coset
enumeration to be used, possible values are <em>“relator_based”</em> or
<em>“coset_table_based”</em>.</p>
</dd>
</dl>
<section id="cosettable">
<h3>CosetTable<a class="headerlink" href="#cosettable" title="Permalink to this headline">¶</a></h3>
<p>Class used to manipulate the information regarding the coset enumeration of
the finitely presented group <code class="docutils literal notranslate"><span class="pre">G</span></code> on the cosets of the subgroup <code class="docutils literal notranslate"><span class="pre">H</span></code>.</p>
<p>Basically a <em>coset table</em> <code class="docutils literal notranslate"><span class="pre">CosetTable(G,H)</span></code>, is the permutation representation
of the finitely presented group on the cosets of a subgroup. Most of the set
theoretic and group functions use the regular representation of <code class="docutils literal notranslate"><span class="pre">G</span></code>, i.e.,
the coset table of <code class="docutils literal notranslate"><span class="pre">G</span></code> over the trivial subgroup.</p>
<p>The actual mathematical coset table is obtained using <code class="docutils literal notranslate"><span class="pre">.table</span></code> attribute and
is a list of lists. For each generator <code class="docutils literal notranslate"><span class="pre">g</span></code> of <code class="docutils literal notranslate"><span class="pre">G</span></code> it contains a column and
the next column corresponds to <code class="docutils literal notranslate"><span class="pre">g**-1</span></code> and so on for other generators, so in
total it has <code class="docutils literal notranslate"><span class="pre">2*G.rank()</span></code> columns. Each column is simply a list of integers.
If <code class="docutils literal notranslate"><span class="pre">l</span></code> is the generator list for the generator <span class="math notranslate nohighlight">\(g\)</span> and if <code class="docutils literal notranslate"><span class="pre">l[i]</span> <span class="pre">=</span> <span class="pre">j</span></code> then
generator <code class="docutils literal notranslate"><span class="pre">g</span></code> takes the coset <span class="math notranslate nohighlight">\(i\)</span> to the coset <span class="math notranslate nohighlight">\(j\)</span> by multiplication from the
right.</p>
<p>For finitely presented groups, a coset table is computed by a Todd-Coxeter
coset enumeration. Note that you may influence the performance of that
enumeration by changing the values of the variable
<code class="docutils literal notranslate"><span class="pre">CosetTable.coset_table_max_limit</span></code>.</p>
</section>
<section id="attributes-of-cosettable">
<h3>Attributes of CosetTable<a class="headerlink" href="#attributes-of-cosettable" title="Permalink to this headline">¶</a></h3>
<p>For <code class="docutils literal notranslate"><span class="pre">CosetTable(G,</span> <span class="pre">H)</span></code> where <code class="docutils literal notranslate"><span class="pre">G</span></code> is the group and <code class="docutils literal notranslate"><span class="pre">H</span></code> is the subgroup.</p>
<ul class="simple">
<li><p><code class="docutils literal notranslate"><span class="pre">n</span></code>: A non-negative integer, non-mutable attribute, dependently
calculated as the maximum among the live-cosets (i.e. <span class="math notranslate nohighlight">\(\Omega\)</span>).</p></li>
<li><p><code class="docutils literal notranslate"><span class="pre">table</span></code>: A list of lists, mutable attribute, mathematically represents the
coset table.</p></li>
<li><p><code class="docutils literal notranslate"><span class="pre">omega</span></code>: A list, dependent on the internal attribute <code class="docutils literal notranslate"><span class="pre">p</span></code>. <span class="math notranslate nohighlight">\(\Omega\)</span>
represents the list of live-cosets. A <em>standard</em> coset-table has its
<span class="math notranslate nohighlight">\(\Omega = \{0, 1, \ldots, index-1 \}\)</span> where <span class="math notranslate nohighlight">\(index\)</span> is the index of subgroup
<span class="math notranslate nohighlight">\(H\)</span> in <span class="math notranslate nohighlight">\(G\)</span>.</p></li>
</ul>
<p>For experienced users we have a number of parameters that can be used to
manipulate the algorithm, like</p>
<ul>
<li><p><code class="docutils literal notranslate"><span class="pre">coset_table_max_limit</span></code> (default value = <span class="math notranslate nohighlight">\(4096000\)</span>): manipulate the maximum
number of cosets allowed in coset enumeration, i.e. the number of rows allowed
in coset table. A coset enumeration will not finish if the subgroup does not
have finite index, and even if it has it may take many more intermediate
cosets than the actual index of the subgroup is. To avoid a coset enumeration
“running away” therefore SymPy has a “safety stop” built-in. This is
controlled by this variable. To change it, use <span class="math notranslate nohighlight">\(max_cosets\)</span> keyword.
For example:</p>
<div class="doctest highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">&gt;&gt;&gt; </span><span class="n">F</span><span class="p">,</span> <span class="n">a</span><span class="p">,</span> <span class="n">b</span> <span class="o">=</span> <span class="n">free_group</span><span class="p">(</span><span class="s2">&quot;a, b&quot;</span><span class="p">)</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">Cox</span> <span class="o">=</span> <span class="n">FpGroup</span><span class="p">(</span><span class="n">F</span><span class="p">,</span> <span class="p">[</span><span class="n">a</span><span class="o">**</span><span class="mi">6</span><span class="p">,</span> <span class="n">b</span><span class="o">**</span><span class="mi">6</span><span class="p">,</span> <span class="p">(</span><span class="n">a</span><span class="o">*</span><span class="n">b</span><span class="p">)</span><span class="o">**</span><span class="mi">2</span><span class="p">,</span> <span class="p">(</span><span class="n">a</span><span class="o">**</span><span class="mi">2</span><span class="o">*</span><span class="n">b</span><span class="o">**</span><span class="mi">2</span><span class="p">)</span><span class="o">**</span><span class="mi">2</span><span class="p">,</span> <span class="p">(</span><span class="n">a</span><span class="o">**</span><span class="mi">3</span><span class="o">*</span><span class="n">b</span><span class="o">**</span><span class="mi">3</span><span class="p">)</span><span class="o">**</span><span class="mi">5</span><span class="p">])</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">C_r</span> <span class="o">=</span> <span class="n">coset_enumeration_r</span><span class="p">(</span><span class="n">Cox</span><span class="p">,</span> <span class="p">[</span><span class="n">a</span><span class="p">],</span> <span class="n">max_cosets</span><span class="o">=</span><span class="mi">50</span><span class="p">)</span>
<span class="gt">Traceback (most recent call last):</span>
  <span class="c">...</span>
<span class="gr">ValueError</span>: <span class="n">the coset enumeration has defined more than 50 cosets</span>
</pre></div>
</div>
</li>
<li><p><code class="docutils literal notranslate"><span class="pre">max_stack_size</span></code> (default value = <span class="math notranslate nohighlight">\(500\)</span>): manipulate the maximum size of
<code class="docutils literal notranslate"><span class="pre">deduction_stack</span></code> above or equal to which the stack is emptied.</p></li>
</ul>
</section>
<section id="compression-and-standardization">
<h3>Compression and Standardization<a class="headerlink" href="#compression-and-standardization" title="Permalink to this headline">¶</a></h3>
<p>For any two entries <span class="math notranslate nohighlight">\(i, j\)</span> with <span class="math notranslate nohighlight">\(i &lt; j\)</span> in coset table, the first
occurrence of <span class="math notranslate nohighlight">\(i\)</span> in a coset table precedes the first occurrence of <span class="math notranslate nohighlight">\(j\)</span> with
respect to the usual row-wise ordering of the table entries. We call such a
table a standard coset table. To standardize a <code class="docutils literal notranslate"><span class="pre">CosetTable</span></code> we use the
<code class="docutils literal notranslate"><span class="pre">.standardize</span></code> method.</p>
<p><strong>Note</strong> the method alters the given table, it does not create a copy.</p>
</section>
</section>
<section id="subgroups-of-finite-index">
<h2>Subgroups of Finite Index<a class="headerlink" href="#subgroups-of-finite-index" title="Permalink to this headline">¶</a></h2>
<p>The functionality in this section are concerned with the construction of
subgroups of finite index. We describe a method for computing all subgroups
whose index does not exceed some (modest) integer bound.</p>
<section id="low-index-subgroups">
<h3>Low Index Subgroups<a class="headerlink" href="#low-index-subgroups" title="Permalink to this headline">¶</a></h3>
<p><code class="docutils literal notranslate"><span class="pre">low_index_subgroups(G,</span> <span class="pre">N)</span></code>: Given a finitely presented group <span class="math notranslate nohighlight">\(G = \left\langle X \mid R \right\rangle\)</span>
(can be a free group), and <code class="docutils literal notranslate"><span class="pre">N</span></code> a positive integer, determine the conjugacy classes of
subgroups of <code class="docutils literal notranslate"><span class="pre">G</span></code> whose indices is less than or equal to <code class="docutils literal notranslate"><span class="pre">N</span></code>.</p>
<p>For example to find all subgroups of <span class="math notranslate nohighlight">\(G = \left\langle a, b \mid a^2 = b^3 = (ab)^4 = 1 \right\rangle\)</span>
having index <span class="math notranslate nohighlight">\(\le\)</span> 4, can be found as follows:</p>
<div class="doctest highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">&gt;&gt;&gt; </span><span class="kn">from</span> <span class="nn">sympy.combinatorics.fp_groups</span> <span class="kn">import</span> <span class="n">low_index_subgroups</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">F</span><span class="p">,</span> <span class="n">a</span><span class="p">,</span> <span class="n">b</span> <span class="o">=</span> <span class="n">free_group</span><span class="p">(</span><span class="s2">&quot;a, b&quot;</span><span class="p">)</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">G</span> <span class="o">=</span> <span class="n">FpGroup</span><span class="p">(</span><span class="n">F</span><span class="p">,</span> <span class="p">[</span><span class="n">a</span><span class="o">**</span><span class="mi">2</span><span class="p">,</span> <span class="n">b</span><span class="o">**</span><span class="mi">3</span><span class="p">,</span> <span class="p">(</span><span class="n">a</span><span class="o">*</span><span class="n">b</span><span class="p">)</span><span class="o">**</span><span class="mi">4</span><span class="p">])</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">l</span> <span class="o">=</span> <span class="n">low_index_subgroups</span><span class="p">(</span><span class="n">G</span><span class="p">,</span> <span class="mi">4</span><span class="p">)</span>
<span class="gp">&gt;&gt;&gt; </span><span class="k">for</span> <span class="n">coset_table</span> <span class="ow">in</span> <span class="n">l</span><span class="p">:</span>
<span class="gp">... </span>    <span class="nb">print</span><span class="p">(</span><span class="n">coset_table</span><span class="o">.</span><span class="n">table</span><span class="p">)</span>
<span class="gp">...</span>
<span class="go">[[0, 0, 0, 0]]</span>
<span class="go">[[0, 0, 1, 2], [1, 1, 2, 0], [3, 3, 0, 1], [2, 2, 3, 3]]</span>
<span class="go">[[0, 0, 1, 2], [2, 2, 2, 0], [1, 1, 0, 1]]</span>
<span class="go">[[1, 1, 0, 0], [0, 0, 1, 1]]</span>
</pre></div>
</div>
<p>This returns the coset tables of subgroups of satisfying the property
that index, <span class="math notranslate nohighlight">\(index\)</span>, of subgroup in group is <span class="math notranslate nohighlight">\(\le n\)</span>.</p>
</section>
</section>
<section id="constructing-a-presentation-for-a-subgroup">
<h2>Constructing a presentation for a subgroup<a class="headerlink" href="#constructing-a-presentation-for-a-subgroup" title="Permalink to this headline">¶</a></h2>
<p>In this section we discuss finding the presentation of a subgroup in a finitely
presentation group. While the <em>subgroup</em> is currently allowed as input only in
the form of a list of generators for the subgroup, you can expect the
functionality of a <em>coset table</em> as input for subgroup in the group in near
future.</p>
<p>There are two ways to construct a set of defining relations for subgroup from
those of <code class="docutils literal notranslate"><span class="pre">G</span></code>. First is on a set of Schreier generators, known generally as
Reidemeister-Schreier algorithm or on the given list of generators of <code class="docutils literal notranslate"><span class="pre">H</span></code>.</p>
<section id="reidemeister-schreier-algorithm">
<h3>Reidemeister Schreier algorithm<a class="headerlink" href="#reidemeister-schreier-algorithm" title="Permalink to this headline">¶</a></h3>
<p>called using <code class="docutils literal notranslate"><span class="pre">reidemeister_presentation(G,</span> <span class="pre">Y)</span></code> where <code class="docutils literal notranslate"><span class="pre">G</span></code> is the group and
<code class="docutils literal notranslate"><span class="pre">Y</span></code> is a list of generators for subgroup <code class="docutils literal notranslate"><span class="pre">H</span></code> whose presentation we want to
find.</p>
<div class="doctest highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">&gt;&gt;&gt; </span><span class="kn">from</span> <span class="nn">sympy.combinatorics.fp_groups</span> <span class="kn">import</span> <span class="n">reidemeister_presentation</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">F</span><span class="p">,</span> <span class="n">x</span><span class="p">,</span> <span class="n">y</span> <span class="o">=</span> <span class="n">free_group</span><span class="p">(</span><span class="s2">&quot;x, y&quot;</span><span class="p">)</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">f</span> <span class="o">=</span> <span class="n">FpGroup</span><span class="p">(</span><span class="n">F</span><span class="p">,</span> <span class="p">[</span><span class="n">x</span><span class="o">**</span><span class="mi">3</span><span class="p">,</span> <span class="n">y</span><span class="o">**</span><span class="mi">5</span><span class="p">,</span> <span class="p">(</span><span class="n">x</span><span class="o">*</span><span class="n">y</span><span class="p">)</span><span class="o">**</span><span class="mi">2</span><span class="p">])</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">H</span> <span class="o">=</span> <span class="p">[</span><span class="n">x</span><span class="o">*</span><span class="n">y</span><span class="p">,</span> <span class="n">x</span><span class="o">**-</span><span class="mi">1</span><span class="o">*</span><span class="n">y</span><span class="o">**-</span><span class="mi">1</span><span class="o">*</span><span class="n">x</span><span class="o">*</span><span class="n">y</span><span class="o">*</span><span class="n">x</span><span class="p">]</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">p1</span> <span class="o">=</span> <span class="n">reidemeister_presentation</span><span class="p">(</span><span class="n">f</span><span class="p">,</span> <span class="n">H</span><span class="p">)</span>
<span class="gp">&gt;&gt;&gt; </span><span class="n">p1</span>
<span class="go">((y_1, y_2), (y_1**2, y_2**3, y_2*y_1*y_2*y_1*y_2*y_1))</span>
</pre></div>
</div>
</section>
</section>
<section id="bibliography">
<h2>Bibliography<a class="headerlink" href="#bibliography" title="Permalink to this headline">¶</a></h2>
<dl class="citation">
<dt class="label" id="cdhw73"><span class="brackets">CDHW73</span></dt>
<dd><p>John J. Cannon, Lucien A. Dimino, George Havas, and Jane M. Watson.
Implementation and analysis of the Todd-Coxeter algorithm. Math. Comp., 27:463–
490, 1973.</p>
</dd>
<dt class="label" id="ho05"><span class="brackets">Ho05</span></dt>
<dd><p>Derek F. Holt,
Handbook of Computational Group Theory.
In the series ‘Discrete Mathematics and its Applications’,
<a class="reference external" href="https://www.crcpress.com/Handbook-of-Computational-Group-Theory/Holt-Eick-OBrien/p/book/9781584883722">Chapman &amp; Hall/CRC 2005, xvi + 514 p</a>.</p>
</dd>
<dt class="label" id="hav91"><span class="brackets">Hav91</span></dt>
<dd><p>George Havas, Coset enumeration strategies.
In Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC’91), Bonn 1991, pages 191–199. ACM Press, 1991.</p>
</dd>
</dl>
</section>
</section>


            <div class="clearer"></div>
          </div>
        </div>
      </div>
      <div class="sphinxsidebar" role="navigation" aria-label="main navigation">
        <div class="sphinxsidebarwrapper">
            <p class="logo"><a href="../../index.html">
              <img class="logo" src="../../_static/sympylogo.png" alt="Logo"/>
            </a></p>
  <h3><a href="../../index.html">Table of Contents</a></h3>
  <ul>
<li><a class="reference internal" href="#">Finitely Presented Groups</a><ul>
<li><a class="reference internal" href="#introduction">Introduction</a><ul>
<li><a class="reference internal" href="#overview-of-facilities">Overview of Facilities</a></li>
</ul>
</li>
<li><a class="reference internal" href="#the-construction-of-finitely-presented-groups">The Construction of Finitely Presented Groups</a></li>
<li><a class="reference internal" href="#free-groups-and-words">Free Groups and Words</a><ul>
<li><a class="reference internal" href="#construction-of-a-free-group">Construction of a Free Group</a></li>
<li><a class="reference internal" href="#construction-of-words">Construction of words</a></li>
</ul>
</li>
<li><a class="reference internal" href="#coset-enumeration-the-todd-coxeter-algorithm">Coset Enumeration: The Todd-Coxeter Algorithm</a><ul>
<li><a class="reference internal" href="#cosettable">CosetTable</a></li>
<li><a class="reference internal" href="#attributes-of-cosettable">Attributes of CosetTable</a></li>
<li><a class="reference internal" href="#compression-and-standardization">Compression and Standardization</a></li>
</ul>
</li>
<li><a class="reference internal" href="#subgroups-of-finite-index">Subgroups of Finite Index</a><ul>
<li><a class="reference internal" href="#low-index-subgroups">Low Index Subgroups</a></li>
</ul>
</li>
<li><a class="reference internal" href="#constructing-a-presentation-for-a-subgroup">Constructing a presentation for a subgroup</a><ul>
<li><a class="reference internal" href="#reidemeister-schreier-algorithm">Reidemeister Schreier algorithm</a></li>
</ul>
</li>
<li><a class="reference internal" href="#bibliography">Bibliography</a></li>
</ul>
</li>
</ul>

  <h4>Previous topic</h4>
  <p class="topless"><a href="tensor_can.html"
                        title="previous chapter">Tensor Canonicalization</a></p>
  <h4>Next topic</h4>
  <p class="topless"><a href="pc_groups.html"
                        title="next chapter">Polycyclic Groups</a></p>
  <div role="note" aria-label="source link">
    <h3>This Page</h3>
    <ul class="this-page-menu">
      <li><a href="../../_sources/modules/combinatorics/fp_groups.rst.txt"
            rel="nofollow">Show Source</a></li>
    </ul>
   </div>
<div id="searchbox" style="display: none" role="search">
  <h3 id="searchlabel">Quick search</h3>
    <div class="searchformwrapper">
    <form class="search" action="https://docs.sympy.org/latest/search.html" method="get">
      <input type="text" name="q" aria-labelledby="searchlabel" autocomplete="off" autocorrect="off" autocapitalize="off" spellcheck="false"/>
      <input type="submit" value="Go" />
    </form>
    </div>
</div>
<script>$('#searchbox').show(0);</script>
        </div>
      </div>
      <div class="clearer"></div>
    </div>
    <div class="related" role="navigation" aria-label="related navigation">
      <h3>Navigation</h3>
      <ul>
        <li class="right" style="margin-right: 10px">
          <a href="../../genindex.html" title="General Index"
             >index</a></li>
        <li class="right" >
          <a href="../../py-modindex.html" title="Python Module Index"
             >modules</a> |</li>
        <li class="right" >
          <a href="pc_groups.html" title="Polycyclic Groups"
             >next</a> |</li>
        <li class="right" >
          <a href="tensor_can.html" title="Tensor Canonicalization"
             >previous</a> |</li>
        <li class="nav-item nav-item-0"><a href="../../index.html">SymPy 1.9 documentation</a> &#187;</li>
          <li class="nav-item nav-item-1"><a href="../index.html" >SymPy Modules Reference</a> &#187;</li>
          <li class="nav-item nav-item-2"><a href="index.html" >Combinatorics</a> &#187;</li>
        <li class="nav-item nav-item-this"><a href="#">Finitely Presented Groups</a></li> 
      </ul>
    </div>
    <div class="footer" role="contentinfo">
        &#169; Copyright 2021 SymPy Development Team.
      Last updated on Sep 30, 2021.
      Created using <a href="https://www.sphinx-doc.org/">Sphinx</a> 4.1.2.
    </div>
  </body>

<!-- Mirrored from docs.sympy.org/latest/modules/combinatorics/fp_groups.html by HTTrack Website Copier/3.x [XR&CO'2014], Sat, 15 Jan 2022 03:28:18 GMT -->
</html>